Prostate (PC), breast (BC) and colorectal (CRC) cancer are the most common and survivable cancers; most survivors of these cancers will be married when diagnosed. Compared to couples that aren't facing a chronic illness, both cancer survivors and their spouses suffer from poorer physical and mental health and higher mortality. Cancer often disrupts the marriage and declines in relationship quality are linked to shorter survival. Exercise has been shown to offer symptomatic relief from side effects of cancer treatment and improve quality of life among cancer survivors; but, has not been used to simultaneously improve the physical and mental health of survivors and spouses and protect the marriage by adapting it to be a shared, team-based activity. Our pilot study of a novel partnered exercise program, Exercising Together, has shown preliminary feasibility and acceptability, but was limited to couples facing PC and fitness outcomes. We propose a larger, more rigorous evaluation of Exercising Together expanding the sample to include couples coping early on with other common cancers, measuring clinically relevant outcomes and including comparison groups that will allow us to distinguish the unique benefits of partnered training on individual and couple health from the possible benefits of exercising in a group with others and/or of engaging both partners in a new health behavior. We plan to conduct a 3-arm, single-blind, parallel design, randomized trial in 294 couples (N=588 participants) coping with PC, BC or CRC, aged 40-70 years old and within 2 years of completion of primary treatment for cancer. Our study compares couples randomized partnered strength training (Exercising Together) in a supervised group setting to (Arm 2) separate supervised group exercise (survivor-only and spouse-only classes) and (Arm 3) separate unsupervised exercise where survivors and spouses exercise on their own at home. Couples will train 2x/wk for 6 months with a 6-month follow-up. The aims of this study are to determine the efficacy of Exercising Together on 1) relationship quality in couples coping with PC, BC, or CRC, 2) physical (body composition, lipids, insulin resistance, blood pressure, inflammation, physical function) and mental (anxiety, depression, fear of recurrence) health of both the survivor and spouse and to evaluate the sustainability and interdependence of benefits from Exercising Together. This study is relevant to public health because the number of cancer survivors and caregivers in the healthcare system will double by 2050, yet there are no programs whatsoever that address the triple threat that cancer poses to the physical and mental health of both survivors and spouses and to their marital relationship. We are the first to focus on the interdependent nature of the couple through partnered exercise that promotes relationship building making this program unlike any other. Exercising Together is a completely new approach to cancer survivorship because it considers the health of the survivor and his/her spouse and their relationship as equally important targets. If successful, this unique approach could be applied to survivors of other cancers or diseases increasing the potential impact of this study.